class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows==0: return ""
        elif numRows==1: return s

        rows = [[] for _ in range(numRows)]
        i = 0
        dir = 1
        for c in s:
            rows[i].append(c)
            i += dir
            if i==(numRows-1) or i==0:dir *= -1
        ret = []
        for row in rows:
            ret.extend(row)
        return ''.join(ret)

print(Solution().convert("PAYPALISHIRING", 3))
